#include<string>
#include<algorithm>
#include "skyline.h"
#include <iostream>

using namespace std;

Skyline::Skyline(int w, int h)
	: width(w), height(h)
{
}

void Skyline::save(vector<Skyline::rect> &rlist){

}

std::vector<Skyline::rect>  Skyline::solve(std::vector<Skyline::rect> rectangles,int *hf)
{

	vector<int>skyline;



	sort(rectangles.begin(),rectangles.end(),comparew);

	for(int i=0;i<width;i++){
		skyline.push_back(0);
	}
	int j=0,k=skyline.size();
	vector<Skyline::rect>ret1;
	for(int i=rectangles.size()-1;i>=0;i--){
		if(rectangles[i].w>width){
			int gap=k-j;
			swap(rectangles[i].h,rectangles[i].w);
			if(gap<rectangles[i].w) break;
			ret1.push_back(rectangles[i]);
			rectangles.erase(rectangles.begin()+i);

			int m=ret1.size()-1;
			ret1[m].x=j;
			ret1[m].y=skyline[j];
			for(int i=j;i<j+ret1[m].w;i++)
				skyline[i]+=ret1[m].h;
			j+=ret1[m].w;
		}
//		cout<<rectangles[i].w<<" "<<rectangles[i].h<<endl;
	}
//	for(int i=0;i<rectangles.size();i++){
//		cout<<rectangles[i].w<<" "<<rectangles[i].h<<endl;
//	}
	int h1,h2,h3;

	vector<Skyline::rect>rlist1=packleftmost(rectangles,skyline,&h1);
	vector<Skyline::rect>rlist2=packtotall(rectangles,skyline,&h2);
	vector<Skyline::rect>rlist3=packtoshort(rectangles,skyline,&h3);
	rlist1.insert(rlist1.begin(),ret1.begin(),ret1.end());
	rlist2.insert(rlist2.begin(),ret1.begin(),ret1.end());
	rlist3.insert(rlist3.begin(),ret1.begin(),ret1.end());
	   //cout<<h1<<" "<<h2<<" "<<h3<<endl;


	if(h1<h2){
		if(h1<h3)
		{
			*hf = h1;
			return rlist1;
		}
		else
		{	*hf = h3;
			return rlist3;
		}
	}else{
		if(h2<h3)
		{
			*hf = h2;
			return rlist2;
		}
		else
		{
			*hf = h3;
			return rlist3;
		}
	}



//	sort(rlist.begin(),rlist.end(),comparew);

}



bool comparew(const Skyline::rect& x, const Skyline::rect& y){
	if(x.w==y.w)return x.h<y.h;
	return x.w<y.w;
}

int Skyline::getlowest(vector<int>& sky){
	int j=0;
	for(int i=0;i<sky.size();i++){
		if(sky[i]<sky[j])j=i;
	}
	return j;
}
bool compare_int(const Skyline::mylist& x, const Skyline::mylist& y){
	return x.length<y.length;
}

vector<int> Skyline::getCombined(vector<Skyline::rect>& rls,vector<int>& sky,int gap,int& mingap)
{
	vector<int> ret;
	vector<mylist> list;
	Skyline::mylist temp;

	int lowest = getlowest(sky);
	//cout<<"lowest="<<lowest<<endl;
	//cout<<"gap = "<<gap<<endl;
	for(int i=0;i<rls.size();i++)
	{
		temp.rect = i;
		temp.length=rls[i].w;
		list.push_back(temp);
		temp.length=rls[i].h;
		list.push_back(temp);
	}

	sort(list.begin(),list.end(),compare_int);
	int comb_min = gap-list[0].length;
	//cout<<comb_min<<" "<<mingap<<endl;
	if(comb_min<mingap)
	{
		return ret;
	}
	int ii=-1,jj=-1;
	for(int i=list.size()-1;i>=0;i--)
	{
		if(list[i].length > gap) continue;

		else
		{
			for(int j=0;j<i;j++)
			{
				if(list[j].length+list[i].length > gap) break;
				if(list[j].rect == list[i].rect) continue;

				if(list[j].length+list[i].length==gap)
				{
				    ret.clear();
					ret.push_back(list[i].rect);
					ret.push_back(list[j].rect);
					comb_min = 0;
					if(list[j].length == rls[list[j].rect].h)
					{
						swap(rls[list[j].rect].h,rls[list[j].rect].w);
					}

					if(list[i].length == rls[list[i].rect].h)
					{
						swap(rls[list[i].rect].h,rls[list[i].rect].w);
					}




                    /*
					rls[list[i].rect].x = lowest;
					rls[list[i].rect].y = sky[lowest];
					cout<<"Got Combined"<<endl;
					cout<<lowest<<" "<<sky[lowest]<<" "<<rls[ret[0]].w<<" "<<rls[ret[0]].h<<endl;

					for(int k=lowest;k<lowest+rls[list[i].rect].w;k++)
					{
						sky[k]+= rls[list[i].rect].h;
					}

					lowest = lowest+rls[list[i].rect].w;

					rls[list[j].rect].x = lowest;
					rls[list[j].rect].y = sky[lowest];
					cout<<lowest<<" "<<sky[lowest]<<" "<<rls[ret[1]].w<<" "<<rls[ret[1]].h<<endl;

					for(int k=lowest;k<lowest+rls[list[j].rect].w;k++)
					{
						sky[k]+= rls[list[j].rect].h;
					}

                    int l = getlowest(sky);
                    cout<<"new lowest = "<<l<<endl;
                    */

			                mingap = 0;
					return ret;

				}

				else if(gap - (list[j].length+list[i].length) < comb_min)
				{
					ret.clear();
					ret.push_back(list[i].rect);
					ret.push_back(list[j].rect);
					comb_min = gap - (list[j].length+list[i].length);

				}

			}
		}
	}
	if(comb_min < mingap)
	{
		mingap = comb_min;
		int len1 = rls[ret[0]].w + rls[ret[1]].w;
		int len2 = rls[ret[0]].w + rls[ret[1]].h;
		int len3 = rls[ret[0]].h + rls[ret[1]].w;
		int len4 = rls[ret[0]].h + rls[ret[1]].h;


		if(gap-len2 == comb_min)
		{
			swap(rls[ret[1]].h,rls[ret[1]].w);
		}

		else if(gap - len3 == comb_min)
		{
			swap(rls[ret[0]].h,rls[ret[0]].w);
		}

		else if(gap - len4 == comb_min)
		{
			swap(rls[ret[0]].h,rls[ret[0]].w);
			swap(rls[ret[1]].h,rls[ret[1]].w);
		}

        /*
		rls[ret[0]].x = lowest;
		rls[ret[0]].y = sky[lowest];

		for(int k=lowest;k<lowest+rls[ret[0]].w;k++)
		{
			sky[k]+= rls[ret[0]].h;
		}
		lowest = lowest+rls[ret[0]].w;

		rls[ret[1]].x = lowest;
		rls[ret[1]].y = sky[lowest];

		for(int k=lowest;k<lowest+rls[ret[1]].w;k++)
		{
			sky[k]+= rls[ret[1]].h;
		}*/

	}

	else
	{
		ret.clear();
	}

	return ret;

}

vector<Skyline::rect> Skyline::packleftmost(vector<Skyline::rect>rls,vector<int>sky,int *hh){
	vector<Skyline::rect> ret;
	while(rls.size()){
/*		cout<<rls.size()<<endl;
		for(int i=0;i<sky.size();i++){
			cout<<sky[i]<<" ";
		}
		cout<<endl;*/
		int j=getlowest(sky);
		int k=j;
		while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
		int gap=k-j;
		int found=0;
		int best=rls.size()-1;
		int mingap=gap;
		if(rls[best].h<gap){
			mingap=gap-rls[best].h;
		}
		if(rls[best].w<gap && gap-rls[best].w<mingap){
			mingap=gap-rls[best].w;
		}

		for(int i=rls.size()-1;i>=0;i--){
			if(rls[i].w==gap){
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h==gap){
				best=i; //changed by jajoo
				swap(rls[i].h,rls[i].w);
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h<gap){
				if(gap-rls[i].h<mingap){
					best=i;
					mingap=gap-rls[i].h;
				}
			}
			if(rls[i].w<gap){
				if(gap-rls[i].w<mingap){
					best=i;
					mingap=gap-rls[i].w;
				}
				break;
			}

		}


		if(!found)
		{
			vector<int> comb = getCombined(rls,sky,gap,mingap);
			if(comb.size() > 0)
			{
		                int lowest = j;
					    rls[comb[0]].x = lowest;
		                rls[comb[0]].y = sky[lowest];

		                for(int k=lowest;k<lowest+rls[comb[0]].w;k++)
		                {
		                    sky[k]+= rls[comb[0]].h;
		                }
		                lowest = lowest+rls[comb[0]].w;

		                rls[comb[1]].x = lowest;
		                rls[comb[1]].y = sky[lowest];

		                for(int k=lowest;k<lowest+rls[comb[1]].w;k++)
		                {
		                    sky[k]+= rls[comb[1]].h;
		                }

				ret.push_back(rls[comb[0]]);
				ret.push_back(rls[comb[1]]);
				rls.erase(rls.begin()+comb[0]);
				rls.erase(rls.begin()+comb[1]);
				found = 1;
			}
		}
                if(!found  && rls[best].w<=gap && mingap==gap-rls[best].w){
			int i=best;
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			ret[m].x=j;
			ret[m].y=sky[j];
			for(int i=j;i<j+ret[m].w;i++)
				sky[i]+=ret[m].h;
			found=1;
		}
		else if(!found && rls[best].h<=gap && mingap==gap-rls[best].h){
			int i=best;
			swap(rls[i].h,rls[i].w);
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			ret[m].x=j;
			ret[m].y=sky[j];
			for(int i=j;i<j+ret[m].w;i++)
				sky[i]+=ret[m].h;
			found=1;
		}
		if(found==0){
			int h1=0,h2=0;
			if(j>0)
				h1=sky[j-1];
			if(k<sky.size())
				h2=sky[k];
			for(int i=j;i<k;i++)
				sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
		}

	}
	//return ret;
	int op=0;
	vector<Skyline::rect> retnew=ret;
	vector<int> skynew=sky;
	while(op==0){
		int maxh=0,max=0;

		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[maxh])maxh=i;
		}
		max=sky[maxh];

		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				if(ret[i].w>=ret[i].h){
					op=1;
					break;
				}

			}
		}
		if(op==1)break;
		int maxr=ret.size()-1;
		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				if(ret[i].h>width){
					op=1;
					break;
				}
				maxr=i;
				//cout<<max<<" "<<maxh<<" "<<maxr<< " "<<ret[maxr].y<<endl;
				//printsky(sky);
				for(int j=ret[maxr].x;j<ret[maxr].x+ret[maxr].w;j++){
					sky[j]-=(ret[maxr].h);
				}
				//printsky(sky);
				swap(ret[maxr].w,ret[maxr].h);
				rls.push_back(ret[maxr]);
				ret.erase(ret.begin()+maxr);
				break;
			}
		}
		while(rls.size()){
			//cerr<<sky[0]<<endl;
			//printsky(sky);
			int j=getlowest(sky);
			int k=j;
			while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
			int gap=k-j;
			int found=0;
			int best=rls.size()-1;

			for(int i=rls.size()-1;i>=0;i--){
				if(rls[i].w<=gap){
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					ret[m].x=j;
					ret[m].y=sky[j];
					//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
					for(int i=j;i<j+ret[m].w;i++)
						sky[i]+=ret[m].h;
					found=1;
					break;
				}
			}


			if(found==0){
				int h1=0,h2=0;
				if(j>0)
					h1=sky[j-1];
				if(k<sky.size())
					h2=sky[k];
				for(int i=j;i<k;i++){
					if(h1==h2 && h1==0){
						//cerr<<j<<" "<<k<<" "<<width<<endl;
						break;
					}
					sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
				}
			}

		}



		int newmaxh=0;
		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[newmaxh])newmaxh=i;
		}
		//cerr<< sky[newmaxh]<< " "<<max<<endl;
		if(sky[newmaxh]<max){
			op=0;
			retnew=ret;
			skynew=sky;
		}
		else{
			op=1;
			ret=retnew;
			sky=skynew;
		}


	}
	int newmaxh=0;
	for(int i=0;i<sky.size();i++){
		if(sky[i]>sky[newmaxh])newmaxh=i;
	}
	*hh=sky[newmaxh];

	//printsky(sky);
	return ret;
}
vector<Skyline::rect> Skyline::packtotall(vector<Skyline::rect>rls,vector<int>sky,int * hh){
	vector<Skyline::rect> ret;
	while(rls.size()){
/*		cout<<rls.size()<<endl;
		for(int i=0;i<sky.size();i++){
			cout<<sky[i]<<" ";
		}
		cout<<endl;*/
		int j=getlowest(sky);
		int k=j;
		while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
		int gap=k-j;
		int found=0;
		int best=rls.size()-1;
		int mingap=gap;
		if(rls[best].h<gap){
			mingap=gap-rls[best].h;
		}
		if(rls[best].w<gap && gap-rls[best].w<mingap){
			mingap=gap-rls[best].w;
		}

		for(int i=rls.size()-1;i>=0;i--){
			if(rls[i].w==gap){
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h==gap){
				best =i; //changed by jajoo
				swap(rls[i].h,rls[i].w);
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h<gap){
				if(gap-rls[i].h<mingap){
					best=i;
					mingap=gap-rls[i].h;
				}
			}
			if(rls[i].w<gap){
				if(gap-rls[i].w<mingap){
					best=i;
					mingap=gap-rls[i].w;
				}
				break; ///changed by jajoo
			}

		}
		if(!found)
		{
			vector<int> comb = getCombined(rls,sky,gap,mingap);
			if(comb.size() > 0)
			{
                int lowest = j;
                if(j==0){
                    rls[comb[0]].x = lowest;
                    rls[comb[0]].y = sky[lowest];

                    for(int p=lowest;p<lowest+rls[comb[0]].w;p++)
                    {
                        sky[p]+= rls[comb[0]].h;
                    }
                    lowest = lowest+rls[comb[0]].w;

                    rls[comb[1]].x = lowest;
                    rls[comb[1]].y = sky[lowest];

                    for(int p=lowest;p<lowest+rls[comb[1]].w;p++)
                    {
                        sky[p]+= rls[comb[1]].h;
                    }
                }

                else if(k==sky.size() || sky[j-1]<sky[k]){
                    rls[comb[0]].x = lowest+mingap;
                    rls[comb[0]].y = sky[lowest+mingap];

                    for(int p=lowest;p<lowest+rls[comb[0]].w;p++)
                    {
                        sky[p+mingap]+= rls[comb[0]].h;
                    }
                    lowest = lowest+rls[comb[0]].w;

                    rls[comb[1]].x = lowest+mingap;
                    rls[comb[1]].y = sky[lowest+mingap];

                    for(int p=lowest;p<lowest+rls[comb[1]].w;p++)
                    {
                        sky[p+mingap]+= rls[comb[1]].h;
                    }
                }
                else{
                    rls[comb[0]].x = lowest;
                    rls[comb[0]].y = sky[lowest];

                    for(int p=lowest;p<lowest+rls[comb[0]].w;p++)
                    {
                        sky[p]+= rls[comb[0]].h;
                    }
                    lowest = lowest+rls[comb[0]].w;

                    rls[comb[1]].x = lowest;
                    rls[comb[1]].y = sky[lowest];

                    for(int p=lowest;p<lowest+rls[comb[1]].w;p++)
                    {
                        sky[p]+= rls[comb[1]].h;
                    }
                }


				ret.push_back(rls[comb[0]]);
				ret.push_back(rls[comb[1]]);
				rls.erase(rls.begin()+comb[0]);
				rls.erase(rls.begin()+comb[1]);
				found = 1;
			}
		}

                if(!found  && rls[best].w<=gap && mingap==gap-rls[best].w){
			int i=best;
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			if(j==0){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else if(k==sky.size()){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else if(sky[j-1]<sky[k]){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else{
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
			}

			found=1;
		}
		else if(!found && rls[best].h<=gap && mingap==gap-rls[best].h){
			int i=best;
			swap(rls[i].h,rls[i].w);
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			if(j==0){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
			}
			else if(k==sky.size()){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else if(sky[j-1]<sky[k]){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else{
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			found=1;
		}
		if(found==0){
			int h1=0,h2=0;
			if(j>0)
				h1=sky[j-1];
			if(k<sky.size())
				h2=sky[k];
			for(int i=j;i<k;i++)
				sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
		}

	}
	//return ret;
	int op=0;
	vector<Skyline::rect> retnew=ret;
	vector<int> skynew=sky;
	while(op==0){
		int maxh=0,max=0;

		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[maxh])maxh=i;
		}
		max=sky[maxh];

		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				if(ret[i].w>=ret[i].h){
					op=1;
					break;
				}

			}
		}
		if(op==1)break;
		int maxr=ret.size()-1;
		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				if(ret[i].h>width){
					op=1;
					break;
				}
				maxr=i;
				//cout<<max<<" "<<maxh<<" "<<maxr<< " "<<ret[maxr].y<<endl;
				//printsky(sky);
				for(int j=ret[maxr].x;j<ret[maxr].x+ret[maxr].w;j++){
					sky[j]-=(ret[maxr].h);
				}
				//printsky(sky);
				swap(ret[maxr].w,ret[maxr].h);
				rls.push_back(ret[maxr]);
				ret.erase(ret.begin()+maxr);
				break;
			}
		}
		while(rls.size()){
			//cerr<<sky[0]<<endl;
			//printsky(sky);
			int j=getlowest(sky);
			int k=j;
			while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
			int gap=k-j;
			int found=0;
			int best=rls.size()-1;

			for(int i=rls.size()-1;i>=0;i--){
				if(rls[i].w==gap){
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					ret[m].x=j;
					ret[m].y=sky[j];
					//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
					for(int i=j;i<j+ret[m].w;i++)
						sky[i]+=ret[m].h;
					found=1;
					break;
				}
				if(rls[i].w<gap){
					int mingap=gap-rls[i].w;
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					if(j==0){
						ret[m].x=j;
						ret[m].y=sky[j];
						for(int i=j;i<j+ret[m].w;i++)
							sky[i]+=ret[m].h;

					}
					else if(k==sky.size()){
						ret[m].x=j+mingap;
						ret[m].y=sky[j];
						for(int i=j+mingap;i<k;i++)
							sky[i]+=ret[m].h;
					}
					else if(sky[j-1]<sky[k]){
						ret[m].x=j+mingap;
						ret[m].y=sky[j];
						for(int i=j+mingap;i<k;i++)
							sky[i]+=ret[m].h;
					}
					else{
						ret[m].x=j;
						ret[m].y=sky[j];
						for(int i=j;i<j+ret[m].w;i++)
							sky[i]+=ret[m].h;
					}
					found=1;
					break;
				}
			}


			if(found==0){
				int h1=0,h2=0;
				if(j>0)
					h1=sky[j-1];
				if(k<sky.size())
					h2=sky[k];
				for(int i=j;i<k;i++){
					if(h1==h2 && h1==0){
						//cerr<<j<<" "<<k<<" "<<width<<endl;
						break;
					}
					sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
				}
			}

		}



		int newmaxh=0;
		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[newmaxh])newmaxh=i;
		}
		//cerr<< sky[newmaxh]<< " "<<max<<endl;
		if(sky[newmaxh]<max){
			op=0;
			retnew=ret;
			skynew=sky;
		}
		else{
			op=1;
			ret=retnew;
			sky=skynew;
		}


	}
	int newmaxh=0;
	for(int i=0;i<sky.size();i++){
		if(sky[i]>sky[newmaxh])newmaxh=i;
	}
	*hh=sky[newmaxh];
	//printsky(sky);
	return ret;
}
vector<Skyline::rect> Skyline::packtoshort(vector<Skyline::rect>rls,vector<int>sky,int *hh){
	vector<Skyline::rect> ret;
	while(rls.size()){
/*		cout<<rls.size()<<endl;
		for(int i=0;i<sky.size();i++){
			cout<<sky[i]<<" ";
		}
		cout<<endl;*/
		int j=getlowest(sky);
		int k=j;
		while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
		int gap=k-j;
		int found=0;
		int best=rls.size()-1;
		int mingap=gap;
		if(rls[best].h<gap){
			mingap=gap-rls[best].h;
		}
		if(rls[best].w<gap && gap-rls[best].w<mingap){
			mingap=gap-rls[best].w;
		}

		for(int i=rls.size()-1;i>=0;i--){
			if(rls[i].w==gap){
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h==gap){
				//i=best;
				swap(rls[i].h,rls[i].w);
				ret.push_back(rls[i]);
				rls.erase(rls.begin()+i);
				int m=ret.size()-1;
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;
				found=1;
				break;
			}
			if(rls[i].h<gap){
				if(gap-rls[i].h<mingap){
					best=i;
					mingap=gap-rls[i].h;
				}
			}
			if(rls[i].w<gap){
				if(gap-rls[i].w<mingap){
					best=i;
					mingap=gap-rls[i].w;
				}
				break;
			}

		}

		if(!found)
		{
			vector<int> comb = getCombined(rls,sky,gap,mingap);
			if(comb.size() > 0)
			{
                int lowest = j;
                if(j==0){
                    rls[comb[0]].x = lowest+mingap;
                    rls[comb[0]].y = sky[lowest+mingap];

                    for(int p=lowest;p<lowest+rls[comb[0]].w;p++)
                    {
                        sky[p+mingap]+= rls[comb[0]].h;
                    }
                    lowest = lowest+rls[comb[0]].w;

                    rls[comb[1]].x = lowest+mingap;
                    rls[comb[1]].y = sky[lowest+mingap];

                    for(int p=lowest;p<lowest+rls[comb[1]].w;p++)
                    {
                        sky[p+mingap]+= rls[comb[1]].h;
                    }
                }

                else if(k==sky.size() || sky[j-1]<sky[k]){
                    rls[comb[0]].x = lowest;
                    rls[comb[0]].y = sky[lowest];

                    for(int p=lowest;p<lowest+rls[comb[0]].w;p++)
                    {
                        sky[p]+= rls[comb[0]].h;
                    }
                    lowest = lowest+rls[comb[0]].w;

                    rls[comb[1]].x = lowest;
                    rls[comb[1]].y = sky[lowest];

                    for(int p=lowest;p<lowest+rls[comb[1]].w;p++)
                    {
                        sky[p]+= rls[comb[1]].h;
                    }
                }
                else{
                    rls[comb[0]].x = lowest+mingap;
                    rls[comb[0]].y = sky[lowest+mingap];

                    for(int p=lowest;p<lowest+rls[comb[0]].w;p++)
                    {
                        sky[p+mingap]+= rls[comb[0]].h;
                    }
                    lowest = lowest+rls[comb[0]].w;

                    rls[comb[1]].x = lowest+mingap;
                    rls[comb[1]].y = sky[lowest+mingap];

                    for(int p=lowest;p<lowest+rls[comb[1]].w;p++)
                    {
                        sky[p+mingap]+= rls[comb[1]].h;
                    }
                }


				ret.push_back(rls[comb[0]]);
				ret.push_back(rls[comb[1]]);
				rls.erase(rls.begin()+comb[0]);
				rls.erase(rls.begin()+comb[1]);
				found = 1;
			}
		}

                if(!found  && rls[best].w<=gap && mingap==gap-rls[best].w){
			int i=best;
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			if(j==0){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			else if(k==sky.size()){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else if(sky[j-1]<sky[k]){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else{
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}

			found=1;
		}
		else if(!found && rls[best].h<=gap && mingap==gap-rls[best].h){
			int i=best;
			swap(rls[i].h,rls[i].w);
			ret.push_back(rls[i]);
			rls.erase(rls.begin()+i);
			int m=ret.size()-1;
			if(j==0){
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;
			}
			else if(k==sky.size()){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else if(sky[j-1]<sky[k]){
				ret[m].x=j;
				ret[m].y=sky[j];
				for(int i=j;i<j+ret[m].w;i++)
					sky[i]+=ret[m].h;

			}
			else{
				ret[m].x=j+mingap;
				ret[m].y=sky[j];
				for(int i=j+mingap;i<k;i++)
					sky[i]+=ret[m].h;

			}
			found=1;
		}
		if(found==0){
			int h1=0,h2=0;
			if(j>0)
				h1=sky[j-1];
			if(k<sky.size())
				h2=sky[k];
			for(int i=j;i<k;i++)
				sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
		}

	}
	//return ret;
	int op=0;
	vector<Skyline::rect> retnew=ret;
	vector<int> skynew=sky;
	while(op==0){
		int maxh=0,max=0;

		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[maxh])maxh=i;
		}
		max=sky[maxh];

		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				if(ret[i].w>=ret[i].h){
					op=1;
					break;
				}

			}
		}
		if(op==1)break;
		int maxr=ret.size()-1;
		for(int i=ret.size()-1;i>=0;i--){
			if(ret[i].y+ret[i].h==max){
				if(ret[i].h>width){
					op=1;
					break;
				}
				maxr=i;
				//cout<<max<<" "<<maxh<<" "<<maxr<< " "<<ret[maxr].y<<endl;
				//printsky(sky);
				for(int j=ret[maxr].x;j<ret[maxr].x+ret[maxr].w;j++){
					sky[j]-=(ret[maxr].h);
				}
				//printsky(sky);
				swap(ret[maxr].w,ret[maxr].h);
				rls.push_back(ret[maxr]);
				ret.erase(ret.begin()+maxr);
				break;
			}
		}
		while(rls.size()){
			//cerr<<sky[0]<<endl;
			//printsky(sky);
			int j=getlowest(sky);
			int k=j;
			while(sky[k]==sky[j]){k++;if(k==sky.size())break;};
			int gap=k-j;
			int found=0;
			int best=rls.size()-1;

			for(int i=rls.size()-1;i>=0;i--){
				if(rls[i].w==gap){
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					ret[m].x=j;
					ret[m].y=sky[j];
					//cout<<ret[m].x<<" "<<ret[m].y<<" "<<ret[m].w<<" "<<ret[m].h<<" "<<endl;
					for(int i=j;i<j+ret[m].w;i++)
						sky[i]+=ret[m].h;
					found=1;
					break;
				}
				if(rls[i].w<gap){
					int mingap=gap-rls[i].w;
					ret.push_back(rls[i]);
					rls.erase(rls.begin()+i);
					int m=ret.size()-1;
					if(j==0){
						ret[m].x=j+mingap;
						ret[m].y=sky[j];
						for(int i=j+mingap;i<k;i++)
							sky[i]+=ret[m].h;

					}
					else if(k==sky.size()){
						ret[m].x=j;
						ret[m].y=sky[j];
						for(int i=j;i<j+ret[m].w;i++)
							sky[i]+=ret[m].h;
					}
					else if(sky[j-1]<sky[k]){
						ret[m].x=j;
						ret[m].y=sky[j];
						for(int i=j;i<j+ret[m].w;i++)
							sky[i]+=ret[m].h;
					}
					else{
						ret[m].x=j+mingap;
						ret[m].y=sky[j];
						for(int i=j+mingap;i<k;i++)
							sky[i]+=ret[m].h;
					}
					found=1;
					break;
				}
			}


			if(found==0){
				int h1=0,h2=0;
				if(j>0)
					h1=sky[j-1];
				if(k<sky.size())
					h2=sky[k];
				for(int i=j;i<k;i++){
					if(h1==h2 && h1==0){
						//cerr<<j<<" "<<k<<" "<<width<<endl;
						break;
					}
					sky[i]=(min(h1,h2))?min(h1,h2):MAX(h1,h2);
				}
			}

		}



		int newmaxh=0;
		for(int i=0;i<sky.size();i++){
			if(sky[i]>sky[newmaxh])newmaxh=i;
		}
		//cerr<< sky[newmaxh]<< " "<<max<<endl;
		if(sky[newmaxh]<max){
			op=0;
			retnew=ret;
			skynew=sky;
		}
		else{
			op=1;
			ret=retnew;
			sky=skynew;
		}


	}
	int newmaxh=0;
	for(int i=0;i<sky.size();i++){
		if(sky[i]>sky[newmaxh])newmaxh=i;
	}
	*hh=sky[newmaxh];
	//printsky(sky);
	return ret;
}
